Until recently, real-time editing of digital images was feasible only on expensive, high-performance computer workstations with dedicated, special-purpose, hardware. The progress of integrated-circuit technology in recent years has produced microprocessors with significantly improved processing power and reduced the cost of memory. These developments have made it feasible to implement image-editing techniques in personal computers.
Software is commercially available with a graphical-user interface (GUI) for selecting and editing a digitally-generated image in a number of ways. For example, to “cut” or delete a portion of the image, the user can employ a mouse to select an area of the image by clicking the left mouse button while the screen “cursor” is located on a corner of the image that is desired to be deleted, dragging the screen “cursor” with the mouse to another corner, thereby outlining a portion or all of the image. Some other image editors permit an operator to enter multiple points defining a polygon having greater than four sides. Image-processing algorithms are then selectively applied over the pixels associated with the polygon.
Regardless of the shape of the selected region, once the user has defined a region of the image, the user then completes the “cut” by either selecting the “cut” command from a drop-down menu (using his mouse and/or a keyboard), or alternatively, by using his mouse to select and activate a GUI “cut” button or icon. In either case, known image-editing software is invoked which performs the “cut” operation, resulting in the original image being replaced by an edited image which has a blanked-out area enclosed by the boundaries of the region so selected.
When a scanner scans a source object (i.e., a photograph, or a text document), a digital image of the original source object is typically generated. The digital image often is stored as a raster or bitmap image. The raster or bitmap image is usually represented in a digital image-processing system by a rectangular grid of pixels, where the pixel is a basic discrete unit for defining bitmap images and has a defined location and color value. A 24-bit digital-image system may be defined by three channels comprising of red (R), green (G), and blue (B), where each channel of color contains 8 bits of information with a range of 0 to 255.
Digitally-stored images may become-skewed during the scanning process, which converts the source object (e.g., a document or a photograph) into binary information that can be processed by an imaging system and/or a computer system. The bitmap image will be skewed if the source object is skewed relative to the scanner platen or when the source object is misaligned by an automatic page feeder, before the scanning operation. Another way that the bitmap image might be skewed relative to the grid of pixels is where the original image is skewed with respect to the paper. This may occur if the image is photocopied and the copy is used as the source object (i.e., the skewed copy is scanned). An image that is skewed during the photocopying process will remain skewed after scanning assuming that the copied source is correctly aligned with the scanner platen and the platen and image sensor are aligned.
When an acquired digital image of the source object is skewed or rotated inside the entire scan image (i.e., inside the entire digital image obtained from the scanner), the acquired digital image typically includes an image of the source content (i.e., the photograph or text of a document), as well as extraneous information (e.g., an image of the underside of a cover from a flatbed scanner). Generally, image rectangles, formed by image acquisition software, are configured with the intention to capture all of the source information within the confines of the image rectangle. If the source is skewed (i.e., misaligned with respect to the rectangular grid), the edges of the digitally-stored image rectangle will generally contain triangular borders of background information.
The background information is introduced because typical scanners traverse the entire available scan region regardless of the size and orientation of the source object on the scanner platen. The resulting bitmap image includes both an image of the source object and extraneous background pixels. This extraneous background information is included in the acquired digital image when the size of the source is relatively small in comparison to the scan region of the scanner. Generally, an operator of the imaging system does not need or desire the background pixels. Furthermore, the extraneous background information is unsightly and increases the data storage capacity required to process and permanently retain the image data. Not only does the extraneous background information within the image rectangle affect the processing throughput of uncompressed image data, but many commonly-used data compression algorithms do not efficiently handle discontinuities such as those that can be expected between the border of a scanned photograph and the extraneous background information. It is known that significant data storage savings can be realized by removing discontinuities from regions in a digital image prior to compressing the digital information.
Prior techniques have been developed to try to detect and correct skewed images. For example, U.S. Pat. No. 4,941,189, entitled, “Optical Character Reader with Skew Recognition,” issued on Jul. 10, 1990, describes a skew correction technique that searches for text characters along a scan line. Another example, U.S. Pat. No. 5,452,374, entitled, “Skew Detection and Correction of a Document Image Representation,” issued on Sep. 19, 1995, describes another technique that segments the scan image into text and non-text regions and then determines the skew from the resulting segmentation. These techniques are insufficient to detect and correct skewed images of scanned photographs. In addition, because photographs can have a variety of sizes and shapes, it is typically difficult to trim the background information from the scanned image of a photograph.
Several techniques have been proposed that detect the skew of a scanned image without requiring the presence of text in the scanned image. One such technique is described in U.S. Pat. No. 5,093,653, entitled, “Image Processing System Having Skew Correction Means,” issued on Mar. 3, 1992. Another such technique is described in U.S. Pat. No. 4,533,959, entitled, “Picture Processing Apparatus,” issued on Aug. 6, 1985. However, these techniques require either human intervention (e.g., U.S. Pat. No. 5,093,653) or special skew detection marks on the original document (e.g., U.S. Pat. No. 4,533,959).
Improvements to the techniques described in U.S. Pat. No. 5,093,653 and U.S. Pat. No. 4,533,959 are described in U.S. Pat. No. 6,310,984 entitled, “Image Processing System With Image Cropping and Skew Correction,” issued on Oct. 30, 2001 and in U.S. Pat. No. 6,360,026, entitled, “Method for Determining a Skew Angle of a Bitmap Image and Deskewing and Auto-Cropping the Bitmap Image,” issued on Mar. 19, 2002. These approaches to removing the background information from the scanned image are computationally intensive and often result in a deskewed image of diminished quality.